package recursion

// 给定一个数组，代表每个人喝完咖啡准备刷杯子的时间
// 只有一台咖啡机，一次只能洗一个杯子，耗费时间a，洗碗才能洗下一杯
// 每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发
// 返回让所有咖啡杯变干净的最早完成使时间
// 三个参数：arr []int, a int, b int


func GetMinCleanTime(arr []int, a int, b int) int {
	if len(arr) == 0 {return 0}
	if b < a { return arr[len(arr)-1] + b}
	return GetMinCleanTimeProcess(arr, 0,0, a, b)
}

func GetMinCleanTimeProcess(arr []int, start ,washLine, a, b int) int {
	if start == len(arr)-1 {
		return Min(Max(washLine, arr[start])+a, arr[start]+b)
	}

	wash := Max(arr[start], washLine)+ a
	// 当前杯洗的最小时间
	next := GetMinCleanTimeProcess(arr, start+1, wash, a, b)
	p1 := Max(wash, next)
	// 当前杯不洗的最小时间
	dry := arr[start] + b
	next2 := GetMinCleanTimeProcess(arr, start+1, washLine, a, b)
	p2 := Max(next2, dry)
	return Min(p1, p2)
}


func GetMinCleanTimeDp(arr []int, a int, b int) int {
	washLineLimit := Max(arr[0]+len(arr)*a, arr[len(arr)-1]+a)
	dp := make([][]int, len(arr))
	for i:=0; i<len(arr); i++ {
		dp[i] = make([]int, washLineLimit+1)
	}
	for i:=0; i<=washLineLimit; i++ {
		if i > arr[len(arr)-1] {
			dp[len(arr)-1][i] = Min(i+a, arr[len(arr)-1]+b)
		} else {
			dp[len(arr)-1][i] = arr[len(arr)-1]+a
		}
	}
	for start:=len(arr)-2; start>=0; start-- {
		for wash:=0; wash<=washLineLimit; wash++ {
			if wash + a > washLineLimit {
				continue
			}
			washT := dp[start+1][Max(arr[start] + a, wash + a)]
			beforeMinTime := dp[start+1][wash]
			drtT := Max(beforeMinTime, arr[start] + b)
			dp[start][wash] = Min(washT, drtT)
		}
	}
	return dp[0][0]
}